class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s1.length();
        int m = s2.length();
        if (n == 0) {
            return s2 == s3;
        } else if (m == 0) {
            return s1 == s3;
        } else if (n + m != s3.length()) {
            return false;
        }
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
        return dpHelper(dp, 0, 0, s1, s2, s3) == 1;
    }

    int dpHelper(vector<vector<int> > &dp,
                  int i, int j,
                  const string &s1,
                  const string &s2,
                  const string &s3) {
        if (dp[i][j]) {
            return dp[i][j];
        }
        if (i == s1.length() && j == s2.length()) {
            return dp[i][j] = 1;
        }
        dp[i][j] = -1;
        if (i < s1.length() && s1[i] == s3[i + j]) {
            if (dpHelper(dp, i + 1, j, s1, s2, s3) == 1) {
                return dp[i][j] = 1;
            }
        }
        if (j < s2.length() && s2[j] == s3[i + j]) {
            if (dpHelper(dp, i, j + 1, s1, s2, s3) == 1) {
                return dp[i][j] = 1;
            }
        }
        return dp[i][j];
    }



};
